COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	TOWARD A THEORY OF HEURISTICS
C00011 ENDMK
C⊗;
TOWARD A THEORY OF HEURISTICS





MOTIVATION


Several recent programs 
in Artificial Intelligence (AI) perform complex tasks demanding
a large corpus of expert knowledge.  Consider, for example, the
MYCIN program for medical diagnosis [ref], the PROSPECTOR program
for evaluating the mineral potential of a site [ref], and
the MOLGEN program for planning experiments in molecular
genetics [ref].   To construct such a system, a knowledge engineer
talks to a human expert, extracts his knowledge, and adds it
to a growing knowledge base usable by a computer program (see Fig. 1).
The critical stage of this process, the limiting step, is the
transfer of expertise.  From the program's point of view, the
limitation is the slow rate at which it acquires knowledge.
This is the central problem facing knowledge egineering today,
the bottleneck of knowledge acquisition.











Figure 1: The bottleneck of knowledge acquisition





Two possible solutions to this problem suggest themselves.  First,
one might try somehow to widen the channel joining expert to program,
for example by building a sophisticated natural language interface.
The difficulty with this is that the expert must communicate not
merely the "facts" of his field, but also the heuristics: the informal
judgmental rules which guide him.  These are rarely thought about
concretely, and almost never appear in journal articles, texts,
or even university courses.  Thus, even with a wider channel, the
expert would have difficulty in verbalizing his heuristics.

The second possible solution is to sever the umbilicus entirely,
eliminate the knowledge engineer and the expert, expose the
program to the environment, let it discover new knowledge on its own.
Can this be done?  The question divides into two parts: can
new domain concepts and relationships be discovered, and can
new domain heuristics be discovered?  This paper is addressed to
these questions, and it presents evidence that the answers are affirmative.


OVERVIEW


The central line of argument is as follows: (see Figure 2)

1. New domains of knowledge d can be developed by using heuristics.
Radically new concepts and relations connecting them can be discovered
by employing a large corpus of heuristics both to suggest plausible
actions and to prune implausible ones.  To accomplish this requires
good heuristics, a good representation for knowledge, and of course a
theory for domain d.

2. As new domains of knowledge emerge and evolve, new heuristics are needed.
A field may change by the introduction of some new device, theory,
technique, paradigm, or observable phenomenon; each time it does so, the
corpus of heuristics useful for dealing with that field may also change.
Consider the body of heuristics useful in planning a trip from
San Francisco to Bern.  Over the last century, many new ones have
been added, and many old ones have undergone revision.  

3. New heuristics can be developed by using heuristics.
The first two points imply that new heuristics must be discovered.
How is this done?  Since "Heuristics" is a domain of knowledge,
like Electronics, or Mathematics, or Travel planning, perhaps
all that is necessary is to set d = Heuristics in (1)  That is,
let the field of heuristics itself grow via heuristic guidance.
To do this would require a good theory of heuristics.

4. As new domains of knowledge emerge and evolve,
new representations are needed.
Just as the potency of a fixed body of heuristics decreases as we
move into new fields, so too does the potency of whatever scheme is being used
to represent knowledge.  Representations must evolve as domain
knowledge accretes.

5. New representations can be developed by using heuristics.
Points (1) and (4) imply that new representations for knowledge must
be devised from time to time, and that existing schemes must change.
How can this happen?  Since "Representation of knowledge" is a field,
just as is Mathematics, or Electronics, or Heuristics, or Travel
planning, perhaps we can somehow set d = Representation in (1).
That is, allow heuristics to manage the development of new
representations.


The final point is that there is no sixth point to make.  These
five statements suffice to solve the central problem, the
bottleneck of automatic knowledge acquisition.
Of course, there is much work to be done on most of these
points; they comprise not so much a solution as a schema for one,
as a research programme to follow.  This paper presents work
to date, by the author, along this programme.  Although the
development parallels the ordering given above, the amount of
space devoted to each point is not uniform. Much of the paper is
concerned with recounting the experience of building AM, a computer
program which searches for interesting new concepts and conjectures
in elementary mathematics (point (1)).  The analysis of AM's
eventual demise provides an illustration of (2).
Much of the remainder is used to develop
the rudiments of a theory of heuristics, which theory is required
for (3).  The paper closes with a detailed example illustrating
(3), (4), and (5).



(1) New domains of knowledge d can be developed by using heuristics.
(2) As new domains of knowledge emerge and evolve, new heuristics are needed.
(3) New heuristics can be developed by using heuristics.
(4) As new domains of knowledge emerge and evolve, new representations are needed.
(5) New representations can be developed by using heuristics.

	Figure 2: Automatic knowledge acquisition via discovery